package chapter7;

import java.util.HashMap;
import java.util.Map;

/**
 * @author yuh
 * @date 2018/5/2 10:41
 * @description
 */
public class Fib {

    static Map<Integer, Integer> map = new HashMap<>();

    static int fib1(int a) {
        if (a == 0) {
            return 0;
        } else if (a == 1) {
            return 1;
        } else {
            return fib1(a - 1) + fib1(a - 2);
        }
    }

    static int fib2(int a) {
        if (a == 0) {
            return 0;
        } else if (a == 1) {
            return 1;
        } else {
            if (map.get(a) == null) {
                map.put(a, fib2(a - 1) + fib2(a - 2));
            }
            return map.get(a);
        }
    }

    static int fib3(int a) {
        int[] arr = new int[a + 1];
        arr[0] = 0;
        arr[1] = 1;
        for (int i = 2; i <= a; i++) {
            arr[i] = arr[i - 1] + arr[i - 2];
        }
        return arr[a];
    }

    static long getTime() {
        return System.currentTimeMillis();
    }

    public static void main(String[] args) {
        long time1 = getTime();
      //  fib1(100);
        long time2 = getTime();
        System.out.println(time2 - time1);
        System.out.println(fib2(10));
        long time3 = getTime();
        System.out.println(time3 - time2);
        System.out.println(fib3(10));
        long time4 = getTime();
        System.out.println(time4 - time3);
    }


}
